package leetcode.code0087;

public class Solution extends Solution87 {

	@Override
	public boolean isScramble(String s1, String s2) {
		if (s1.equals(s2))
			return true;
		int len = s1.length();
		char[] cs1 = s1.toCharArray();
		char[] cs2 = s2.toCharArray();
		if (notPass(cs1, cs2)) {
			return false;
		}
		Boolean[][][] dp = new Boolean[len][len][len + 1];
		return this.f(cs1, 0, cs2, 0, len, dp);
	}

	public boolean notPass(char[] cs1, char[] cs2) {
		int[] dic = new int[128];
		for (char c : cs1) {
			dic[c]++;
		}
		for (char c : cs2) {
			dic[c]--;
		}
		for (int i : dic) {
			if (i != 0)
				return true;
		}
		return false;
	}

	private boolean f(char[] cs1, int l1, char[] cs2, int l2, int len, Boolean[][][] dp) {
		if (len == 1) {
			dp[l1][l2][len] = cs1[l1] == cs2[l2];
			return cs1[l1] == cs2[l2];
		}
		if (dp[l1][l2][len] != null)
			return dp[l1][l2][len];
		for (int i = 0; i < len - 1; i++) {// 不能等于len
			boolean p1 = this.f(cs1, l1, cs2, l2, i + 1, dp);
			if (p1) {
				boolean p2 = this.f(cs1, l1 + i + 1, cs2, l2 + i + 1, len - i - 1, dp);
				if (p2) {
					dp[l1][l2][len] = true;
					return true;
				}
			}
			p1 = this.f(cs1, l1, cs2, l2 + len - 1 - i, i + 1, dp);
			if (p1) {
				boolean p2 = this.f(cs1, l1 + i + 1, cs2, l2, len - i - 1, dp);
				if (p2) {
					dp[l1][l2][len] = true;
					return true;
				}
			}
		}
		dp[l1][l2][len] = false;
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
